package org.shj.dhsjjg.primarypath;

import java.util.Stack;

//求关键路径，首先把图转化为邻接表
//计算各结点的最早以及最晚开始时间，
public class Main {

	public static void main(String[] args) {
		GraphAdjList graph = new GraphAdjList();
		VertexNode[] nodes = graph.init();
		CriticalPath(nodes);
	}
	
	public static void CriticalPath(VertexNode[] nodes){
		Stack<VertexNode> stack2 = new Stack<VertexNode>();//拓扑序列的栈
		int[] etv = new int[nodes.length]; //最早开始时间的数组
		for(int i = 0 ; i < nodes.length; i++){
			etv[i] = 0; //初始化为0
		}
		
		EdgeNode en;
		int gettop, k;
		
		topoSort(nodes, etv, stack2);
		
		int[] ltv = new int[nodes.length]; //最晚发生时间的数组
		for(int i = 0 ; i < nodes.length; i++){
			ltv[i] = etv[nodes.length - 1];//初始化为最早发生时间
		}
		
		VertexNode vn = null;
		while(!stack2.isEmpty()){
			vn = stack2.pop();
			gettop = vn.getData();
			
			en = vn.getFirstEdge();
			while(en != null){
				k = en.getAdjvex();
				if(ltv[k] - en.getWeight() < ltv[gettop]){ //各顶点事件最晚发生时间
					ltv[gettop] = ltv[k] - en.getWeight();
				}
				
				en = en.getNext();
			}
		}
		
		int ete, lte; //声明活动最早发生时间和最迟发生时间变量
		//求 ete, lte和关健活动
		for(int j = 0 ; j < nodes.length; j++){
			en = nodes[j].getFirstEdge();
			while(en != null){
				k = en.getAdjvex();
				ete = etv[j]; //活动最早发生时间
				lte = ltv[k] - en.getWeight();//活动最迟发生时间
				
				if(ete == lte){ //两者相等即在关健路径上
					System.out.println("<V" + nodes[j].getData() + ",V" + nodes[k].getData() + "> lenth: " 
								+ en.getWeight() + ", ");
				}
				en = en.getNext();
			}
		}
	}
	
	public static void topoSort(VertexNode[] nodes, int[] etv, Stack<VertexNode> stack2){
		EdgeNode en;
		int i,k, gettop;
		int count = 0;
		Stack<VertexNode> stack = new Stack<VertexNode>();
		
		for(i = 0; i < nodes.length; i++){
			if(nodes[i].getIn() == 0){ //入度为0的结点，即开始结点
				stack.push(nodes[i]); 
			}
		}
		
		VertexNode vn = null;
		
		while(!stack.isEmpty()){
			count++;
			vn = stack.pop();
			gettop = vn.getData(); //弹出顶点的序号
			stack2.push(vn);//将弹出的顶点序号压入拓扑序列的栈
			en = vn.getFirstEdge();
			
			while(en != null){
				k = en.getAdjvex();
				nodes[k].setIn(nodes[k].getIn() - 1);//k结点的前序结点已经弹出一个了，所以把k结点的入度减1
				
				if(nodes[k].getIn() == 0 ){
					stack.push(nodes[k]);
				}
				
				//当前顶点最早发生时间值 + 该点至其邻接点(k点)的值  > k点最早发生的时间值 
				if(etv[gettop] + en.getWeight() > etv[k]){ //求各顶点事件最早发生时间值
					etv[k] = etv[gettop] + en.getWeight();
				}
				
				en = en.getNext();
			}
		}
		
		if(count < nodes.length){
			//存在环路，数据有问题。
		}else{
			
		}
	}

}
